package 每日一题;

import 字节.LRU;

import java.util.HashMap;

class Node{
    int key;
    int val;
    Node next;
    Node pre;
    public Node(){};
    public Node(int key,int val){this.key=key; this.val=val;}

}

public class LRUCache {
    HashMap<Integer, Node> hashMap;
    Node head;
    Node tail;
    int size=0;
    public LRUCache(int capacity){
        this.size=capacity;
        hashMap=new HashMap<>(capacity);
    }

    int get(int key){
        Node node=hashMap.get(key);
        if(node==null){
            return -1;
        }else {
            makeRecently(node);
            return node.val;
        }
    }
    void put(int key,int val){
        Node node=hashMap.get(key);
        if(node!=null){
            /**************    关键点 不可新建节点     ***************/
            node.val=val;
            hashMap.put(key,node);
            makeRecently(node);
        }else {
            if(hashMap.size()==size){
                removeLast();
            }
            Node node1=new Node(key,val);
            addToHead(node1);
            hashMap.put(key,node1);

        }
    }
    void removeLast(){
        hashMap.remove(tail.key);
        Node node1=tail.pre;
        if(node1!=null){
            node1.next=null;
            tail=node1;
        }
    }
    void makeRecently(Node node){
        if(node==head){
            return;
        } else if (node==tail) {
            tail.pre.next=null;
            tail=tail.pre;
        }else {
            remove(node);
        }
        addToHead(node);
    }
    void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }
    void addToHead(Node node){
        if(hashMap.isEmpty()){
            head=node;
            tail=node;
            return;
        }
        node.next=head;
        head.pre=node;
        head=head.pre;
    }

    public static void main(String[] args) {
        LRUCache lruCache=new LRUCache(2);
        lruCache.put(2,1);
        lruCache.put(2,2);
        lruCache.get(2);
        lruCache.put(1,1);
        lruCache.put(4,1);
        lruCache.get(2);
    }
}
